Due to the continually increasing demands for computing power and speed, the use of multiprocessor networks has been continually brought to the fore for handling computational problems. However, when it comes to the design and programming of efficient multiprocessor systems, a number of problems are presented among which are the problems of synchronizing various of the processes used and maintaining data coherence plus the proper ordering of events. These are all factors which must be addressed by the designer.
In a multiprocessor system, there is generally an instruction set which contains basic instructions used for the handling of synchronization and communication between various processing activities.
In these situations, the concept of "communication" refers to the exchange of data between different processing activities while the concept of "synchronization" is a special type of communication in which the data transferred is involved with control data information. Synchronization is used for the dual purpose of regulating the proper sequencing of processes and for insuring mutually exclusive access to certain shared data. The multiprocessor systems which use shared-memory will provide for the handling of communication and synchronization by the use of the controlled sharing of data in memory.
A major problem involved in these systems is that of memory coherence which involves the system's ability to execute memory operations correctly. Multiprocessor systems also have a requirement for sequential consistency which means that there must be a certain order in the allowable sequence of executive instructions during the same process activity which may be shared by different processors. For example, it may be noted that when two concurrent processors are operating, they can effect each others execution through the sharing of writable data and the sending of interrupt signals, but it is the order of these events that is of significant importance. Accesses to shared writable (alterable) data should be executed in a mutually exclusive manner.
The problem of "coherency" is an ever-present problem in that contradictory information or inconsistencies can occur between various ones of the memories involved. As an example, in a computer having a processor and main memory together with a cache, it may be found that the cache and main memory may contain inconsistent copies (contradictory) of data. Thus multiple cache memories could possess different copies of the same memory block due to the fact that one or more of the processors has modified its own private copy. This type of inconsistency could possibly affect correct execution of a program.
Thus the problem of inconsistency or "cache incoherence" can occur due to the following: (a) sharing of writable data; (b) process migration; (c) I/O activity.
In some systems the process activity is allowed to migrate, that is to be scheduled in different processors in order to balance the workload. When this occurs in a multiprocessor system whereby each processor has its own private cache, then data inconsistencies can result.
Previous methods of handling the coherency of memory or handling of data inconsistency have included the following techniques: (i) to use only shared cache memories which are associated with the main memory module and not permit any "private" cache memory for each individual processor; (ii) attaching a private cache memory to each processing unit, but operating such that any "shared writable data" is not permitted in the cache memory. This type of data is called "non-cachable". The instructions and other data, which can be copied into cache memory, would be referred to as "cachable". However, in this situation, the data must be tagged as to whether it is cachable or noncachable; (iii) tagging of shared writable data as noncachable and in this case, the performance of the system is considerably diminished; (iv) a system which allow shared writable data to exist in multiple cache memories but which requires a centralized global table which stores the status of memory blocks so that coherence enforcement signals can be generated on the basis of the status of the memory block; (v) the use of a "snooping" cache controller which can be used in bus-oriented multiple processors having a table that records the status of each memory block and which can be efficiently distributed among the processors involved. Consistency between the cache memories here is maintained by a bus-watching mechanism called the "snooping cache controller" which implements the cache coherency protocol on the bus.
For example, in a multiprocessor network, where each processor has its own private cache memory, the snooping controllers are used to watch the system bus for the "Store" command. If a store operation is made to a location in a cache memory, then the "copies" of this block of memory in the cache are updated.
A detailed discussion of the various problems involved in such type of multiprocessor systems is discussed in a Feb. 1988 article entitled "Synchronization, Coherence, and Event Ordering in Multiprocessors" (pages 9 through 21 in Computer, published by IEEE, by the authors Dubois, Scheurich, and Briggs).
The present disclosure provides improved methods for handling the coherency problems in multiprocessor systems by the provision of a snooping cache coherency protocol for shared bus multiprocessors. The improved system provides for the update of the cache memory and an image directory unit on a serial basis often designated as "non-atomic" which is to indicate that the updates are done at different times and not concurrently. The non-atomicity of the directory updates thus allows for the processor-to-cache memory cycle time to be minimized and provide for a higher performance throughput.